package 力扣;

public class Leedcode1201丑数3 {
    private  long a,b,c;
    private  long ab,ac,bc;
    private long abc;
    public int nthUglyNumber(int n, int a, int b, int c) {
        //求出a,b,c,ab,ac,bc,abc的公倍数，判单重复计算
        ab = lcm(a,b);
        ac = lcm(a,c);
        bc = lcm(b,c);
        abc = lcm(ab,c);

        this.a = a;
        this.b = b;
        this.c = c;
        int left = Math.min(a,Math.min(b,c));
        int right = (int) Math.pow(10,9);
        while (left < right){
            int mid = (right-left)/2 + left;
            if (minor(mid,n)){
                left = mid+1;
            }else {
                right = mid;
            }
        }
        return left;
    }

    private boolean minor(int mid, int n) {
        return mid/a + mid/b + mid/c + mid/abc - mid/ab - mid/ac - mid/bc < n;
    }

    /**
     * 求ab的最新奥公倍数的方法
     * @param a
     * @param b
     * @return
     */
    private long lcm(long a, long b) {
        return a*b/gcm(a,b);
    }

    /**
     * 求ab的最小公约数的方法
     * @param a
     * @param b
     * @return
     */
    private long gcm(long a, long b) {
        return b == 0 ? a : gcm(b,a%b);
    }
}
